053 - Discrete Dowsing（★7）
三分探索をするとクエリ回数が多すぎるので、前の結果を最利用する。
三分探索のように$ (L,p,q,R) として区間の幅を縮めていくが、$ p,q の情報を捨てるのは惜しい。
区間の分割の比が常に一定になるように分割すれば一定の割合で収束する。これは連続関数の場合は黄金分割探索、離散の場合はフィボナッチ探索として知られている。
$ (0,F_{m-2},F_{m-1},F_m) から開始し、$ A_p>A_qならば$ (L,p,q,R) \to (L,L+R-p,p,q)に、$ A_p \leq A_qならば$ (L,p,q,R) \to (p,q,L+R-q,R) に変化させればよい。
黄金分割探索は連続系アルゴリズムの授業で出てきたので知っていた。フィボナッチ探索は全体で見ても難しいと思う。